package io.adrainty.algorithm.mars;

/**
 * 数字分组求偶数和
 *
 * @author AdRainty
 * @version V1.0.0
 * @link <a href="https://www.marscode.cn/practice/364l85wv6oo6lq?problem_id=7414004855076077612">...</a>
 * @since 2024/11/21 下午9:39
 */
public class Solution004 {

    private Solution004() {}

    public static int solution(int[] numbers) {
        // Please write your code here
        int[][] matrix = countOddEven(numbers);
        return calculateCombinations(matrix);
    }

    /**
     * 统计每个数字的奇偶性
     *
     * @param numbers 数字数组
     * @return 对numbers[i], matrix[i][0]为偶数的个数 matrix[i][1]为奇数的个数
     */
    private static int[][] countOddEven(int[] numbers) {
        int[][] matrix = new int[numbers.length][2];
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == 0) {
                matrix[i][0] = 1;
            } else {
                int[] hash = new int[10];
                while (numbers[i] != 0) {
                    // 排除重复数字
                    int digit = numbers[i] % 10;
                    if (hash[digit] == 1) continue;
                    hash[digit] = 1;

                    // 计算奇偶性
                    if (digit % 2 == 0) {
                        matrix[i][0]++;
                    } else {
                        matrix[i][1]++;
                    }
                    numbers[i] /= 10;
                }
            }
        }
        return matrix;
    }

    /**
     * 计算所有可能的组合
     *
     * @param matrix 奇偶数统计矩阵
     * @return 满足条件的组合数
     */
    private static int calculateCombinations(int[][] matrix) {
        return calculateCombinationsHelper(matrix, 0, 0);
    }

    /**
     * 递归计算组合
     *
     * @param matrix   奇偶数统计矩阵
     * @param index    当前处理的数字组索引
     * @param oddCount 当前选择的奇数个数
     * @return 满足条件的组合数
     */
    private static int calculateCombinationsHelper(int[][] matrix, int index, int oddCount) {
        // 如果已经处理完所有数字组
        if (index == matrix.length) {
            // 如果奇数个数为偶数，则当前组合的和为偶数
            return oddCount % 2 == 0 ? 1 : 0;
        }

        // 选择当前数字组的奇数
        int countWithOdd = calculateCombinationsHelper(matrix, index + 1, oddCount + 1);

        // 选择当前数字组的偶数
        int countWithEven = calculateCombinationsHelper(matrix, index + 1, oddCount);

        // 返回两种选择的组合数之和
        return countWithOdd * matrix[index][1] + countWithEven * matrix[index][0];
    }

}
